#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

//int count;
////int ret;
//void dfs(TreeNode* root)
//{
//	if (root == nullptr) return;
//	dfs(root->left);
//	::count--;
//	if (::count == 0) ::ret = root->val;
//	dfs(root->right);
//}
//int kthSmallest(TreeNode* root, int k) 
//{
//	::count = k;
//	dfs(root);
//	return ret;
//}
//vector<string> ret;
//void dfs(TreeNode* root, string s)
//{
//	if (root->left == nullptr && root->right==nullptr)
//	{
//		s += to_string(root->val);
//		ret.push_back(s);
//		return;
//	}
//	s += to_string(root->val);
//	s += '->';
//	dfs(root->left, s);
//	dfs(root->right, s);
//}
//vector<string> binaryTreePaths(TreeNode* root) {
//	dfs(root, "");
//	return ret;
//}
//vector<vector<int>> ret;
//vector<int> path;
//vector<bool> check;
//void dfs(vector<int>& nums)
//{
//	if (path.size() == nums.size())
//	{
//		ret.push_back(path);
//		return;
//	}
//	for (int i = 0; i < nums.size(); i++)
//	{
//		if (check[i] == false)
//		{
//			check[i] = true;
//			path.push_back(nums[i]);
//			dfs(nums);
//			path.pop_back();
//			check[i] = false;
//		}
//	}
//}
//vector<vector<int>> permute(vector<int>& nums) {
//	check.resize(nums.size(), false);
//	dfs(nums);
//	return ret;
//}
//vector<vector<int>> ret;
//vector<int> path;
//void dfs(vector<int> nums, int pos)
//{
//	ret.push_back(path);
//	for (int i = pos; i < nums.size(); i++)
//	{
//		path.push_back(nums[i]);
//		dfs(nums, pos + 1);
//		path.pop_back();
//	}
//}
//vector<vector<int>> subsets(vector<int>& nums) {
//	dfs(nums,0);
//	return ret;
//}
//int path;
//int sum;
//void dfs(vector<int>& nums, int pos)
//{
//	sum += path;
//	for (int i = pos; i < nums.size(); i++)
//	{
//		path |= nums[i];
//		dfs(nums, i + 1);
//		path |= nums[i];
//	}
//}
//int subsetXORSum(vector<int>& nums) {
//	dfs(nums, 0);
//	return sum;
//}
//vector<vector<int>> ret;
//vector<int> path;
//vector<bool> check;
//void dfs(vector<int>& nums)
//{
//	if (path.size() == ret.size())
//	{
//		ret.push_back(path);
//		return;
//	}
//	for (int i = 0; i < nums.size(); i++)
//	{
//		if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true))
//		{
//			path.push_back(nums[i]);
//			check[i] = true;
//			dfs(nums);
//			path.pop_back();
//			check[i] = false;
//		}
//	}
//}
//vector<vector<int>> permuteUnique(vector<int>& nums) {
//	check.resize(nums.size(), false);
//	sort(nums.begin(), nums.end());
//	dfs(nums);
//	return ret;
//}

int main()
{

	return 0;
}